import java.util.LinkedList;
import java.util.Queue;

public class Solution2 {
    int m;
    int n;
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    boolean[][] check;
    Queue<int[]> q;
    public int numEnclaves(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        check = new boolean[m][n];
        q = new LinkedList<>();

        for(int i = 0; i < m; i++) {
            if(grid[i][0] == 1 && check[i][0] == false) {
                check[i][0] = true;
                bfs(grid, i, 0);
            }
            if(grid[i][n - 1] == 1 && check[i][n - 1] == false) {
                check[i][n - 1] = true;
                bfs(grid, i, n - 1);
            }
        }
        for(int j = 0; j < n ; j++) {
            if(grid[0][j] == 1 && check[0][j] == false) {
                check[0][j] = true;
                bfs(grid, 0, j);
            }
            if(grid[m - 1][j] == 1 && check[m - 1][j] == false) {
                check[m - 1][j] = true;
                bfs(grid, m - 1, j);
            }
        }

        int ret = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1 && check[i][j] == false) {
                    ret++;
                }
            }
        }
        return ret;
    }

    public void bfs(int[][] grid, int i, int j) {
        q.add(new int[]{i, j});
        while(!q.isEmpty()) {
            int sz = q.size();
            for(int count = 0; count < sz; count++) {
                int[] t = q.poll();
                int a = t[0];
                int b = t[1];
                for(int k = 0; k < 4; k++) {
                    int x = a + dx[k];
                    int y = b + dy[k];
                    if(x >= 0 && x < m && y >= 0 && y < n && check[x][y] == false && grid[x][y] == 1) {
                        check[x][y] = true;
                        q.add(new int[]{x, y});
                    }
                }
            }
        }
    }

    public int numEnclaves2(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        check = new boolean[m][n];
        q = new LinkedList<>();
        // 1. 把边上的 1 全部加入队列中
        for(int i = 0; i < m; i++) {
            if(grid[i][0] == 1 && check[i][0] == false) {
                check[i][0] = true;
                q.add(new int[]{i, 0});
            }
            if(grid[i][n - 1] == 1 && check[i][n - 1] == false) {
                check[i][n - 1] = true;
                q.add(new int[]{i, n - 1});
            }
        }
        for(int j = 0; j < n ; j++) {
            if(grid[0][j] == 1 && check[0][j] == false) {
                check[0][j] = true;
                q.add(new int[]{0, j});
            }
            if(grid[m - 1][j] == 1 && check[m - 1][j] == false) {
                check[m - 1][j] = true;
                q.add(new int[]{m - 1, j});
            }
        }
        bfs2(grid);

        int ret = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1 && check[i][j] == false) {
                    ret++;
                }
            }
        }
        return ret;
    }
    // 多源 bfs
    public void bfs2(int[][] grid) {
        while(!q.isEmpty()) {
            int sz = q.size();
            for(int count = 0; count < sz; count++) {
                int[] t = q.poll();
                int a = t[0];
                int b = t[1];
                for(int k = 0; k < 4; k++) {
                    int x = a + dx[k];
                    int y = b + dy[k];
                    if(x >= 0 && x < m && y >= 0 && y < n && check[x][y] == false && grid[x][y] == 1) {
                        check[x][y] = true;
                        q.add(new int[]{x, y});
                    }
                }
            }
        }
    }
}
